/********************** 定义与初始化 ***********************************/
struct node {
    int key;
    int val;
    struct node *prev;
    struct node *next;  
};
typedef struct {
    int key;        
    struct node *map;
    UT_hash_handle hh; //make this structure hashable
} uthash_t;

typedef struct {
    int capacity;   //cache容量
    struct node *head; //循环双向链表的表头，最新的节点在头，最少用的节点在尾
    uthash_t *uthash;
} LRUCache;

LRUCache* lRUCacheCreate(int capacity) {
    int i;
    LRUCache* me = malloc(sizeof(*me));
    me->capacity = capacity;

    //初始化循环双向链表
    me->head = malloc(sizeof(struct node));
    me->head->next = me->head;
    me->head->prev = me->head;
    
    me->uthash = NULL;   //哈希结构体指针必须初始化为NULL
    return me;
}

/********************** 双向链表操作 ***********************************/

//目标节点从双向链表中脱离
void drop_node_dll(struct node *node)
{
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
void insert_head_dll(struct node *head, struct node *node)
{
    node->next = head->next; node->prev = head;
    head->next->prev = node; head->next = node; 
}

/********************** LRU操作 ***********************************/
int lRUCacheGet(LRUCache* obj, int key) {
    uthash_t *ret;
    HASH_FIND_INT(obj->uthash, &key, ret);
    if (ret == NULL) return -1;
    else {
        drop_node_dll(ret->map);
        insert_head_dll(obj->head, ret->map);
        return ret->map->val;
    }
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    uthash_t *ret;
    HASH_FIND_INT(obj->uthash, &key, ret);
    if (ret != NULL) {    //如果key存在，更新节点值，且将节点的位置调整到链表头
        ret->map->val = value;
		//是头节点
		if (ret->map == obj->head->next) 
            return ;

        drop_node_dll(ret->map);
        insert_head_dll(obj->head, ret->map);
    }
    else {  //如果不存在，则插入
        struct node *new_node = malloc(sizeof(struct node));
        new_node->val = value;
        new_node->key = key;

        uthash_t *new_map = malloc(sizeof(uthash_t));
        new_map->key = key;
        new_map->map = new_node;
        

        if (HASH_COUNT(obj->uthash) >= obj->capacity) {    //如果缓存已满，取消尾节点在哈希表中的映射，释放内存
            struct node *save = obj->head->prev;
            drop_node_dll(save);

            HASH_FIND_INT(obj->uthash, &save->key, ret);            
            HASH_DEL(obj->uthash, ret);   
            free(ret->map); ret->map = NULL;
        }
        //插入新节点
        HASH_ADD_INT(obj->uthash, key, new_map); 
        insert_head_dll(obj->head, new_node);
    }
}

void lRUCacheFree(LRUCache* obj) {
    int i;
    uthash_t *del, *temp;
    free(obj->head);
    /* free the hash table contents */
    HASH_ITER(hh, obj->uthash, del, temp) {
      HASH_DEL(obj->uthash, del);
      free(del->map);
    }
    free(obj);
}